package j2024.j202409;

import java.util.Arrays;

public class j0915 {
    /**
     * 88. 合并两个有序数组
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     *
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     *
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
     * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。
     * nums2 的长度为 n 。
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int ai = m-1;
        int bi = n-1;
        int i = m+n-1;
        while(ai>=0 || bi>=0){
            if(ai<0){
                nums1[i--] = nums2[bi--];
            }else if(bi<0){
                nums1[i--] = nums2[ai--];
            }else if(nums1[ai]>nums2[bi]){
                nums1[i--] = nums1[ai--];
            }else {
                nums1[i--] = nums2[bi--];
            }
        }
    }

    /**
     * 27. 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。
     * 然后返回 nums 中与 val 不同的元素的数量。
     *
     * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
     *
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
     * nums 的其余元素和 nums 的大小并不重要。
     * 返回 k。
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != val){
                nums[count++] = nums[i];
            }
        }
        return count;
    }

    /**
     * 26. 删除有序数组中的重复项
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
     * 元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     *
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     *
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。
     * nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     * @param nums
     * @return
     */
    public int removeDuplicates1(int[] nums) {
        int n = nums.length;
        if(n==0){
            return 0;
        }
        int slow = 1,fast = 1;
        while(fast<n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }

    /**
     * 80. 删除有序数组中的重复项 II
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，
     * 返回删除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
         int n = nums.length;
         if(n<=2){
             return n;
         }
         int slow = 2,fast = 2;
         while(fast<n){
             if(nums[slow-2]!=nums[fast]){
                 nums[slow++] = nums[fast];
             }
             fast++;
         }
         return slow;
    }

    /**
     * 169. 多数元素
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。
     * 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     *
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        return nums[n/2];
    }
}
